package first_practice;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-42接雨水
 * @date 2025/3/12 19:47
 */
public class Solution42 {
    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        trap(nums);
    }

    public static int trap(int[] height) {
        int n = height.length;
        int[] f = new int[n];
        int[] l = new int[n];
        f[0] = height[0];
        l[n - 1] = height[n - 1];
        int ans = 0;
        for (int i = 1; i < n; i++) {
            f[i] = Math.max(f[i - 1], height[i]); // 每个元素的左侧最大值（包括它自身）
            l[n - i - 1] = Math.max(l[n - i], height[n - i - 1]); // 每个元素的右侧最大值（包括它自身）
        }
        for (int i = 0; i < n; i++) {
            ans += Math.min(f[i], l[i]) - height[i];
        }
        return ans;
    }
}
